User blog:PsiCubed2/Offtopic question about a mathematical problem
Since some people here have strong backgrounds in number theory, I figured I'll ask this here: Suppose I have a semprime N that factors into two distinct primes of a similar size p and q. We all know that if N is large enough, it would impractical to factor it (that's how RSA works). But is there a practical way to derive some information on the digits of p and q? If anyone is interested why I'm asking, here's the deal: I'm mastering an rpg game and I want to give my players a secret document that has the following properties: (1) They get an actual encrypted document (a string of numbers on a piece of paper) at a certain point in time, which wel'll call "Time A". (2) They are supposed to find "the key" at a later point in time, which we'll call "Time B". (3) Given the key, the decryption process should be possible to do by hand with the aid of nothing more than a pocket calculator (which means that actually using RSA is not an option). (4) Without the key, the code should be practically unbreakable by a serious hobbyist making a reasonable effort. It doesn't have to be completely crackproof, but it does need to be reasonably secure against curious players with a great deal of math background (and a certain animosity regarding GM-held secrets ;-)) (5) Due to fairness issues, I want my players to have a way to verify that I'm not secretly changing the plaintext between Time A and Time B (which is why a simple one time pad won't work here). With these conditions mind, here is the encryption scheme I've dreamt up for this purpose: (1) Let k>150 be then number of letters in the secret message. (2) We pick a semiprime N=pq which has 2k digits. (3) We ''concatanate ''the digits of p and q (smallest first) to create a onetime pad cipher. (4) We turn the message into numbers (A=01, B=02, C=03,.... Z=26) and use the digits of the onetime pad (mod 100) to scramble the message. (5) On the piece of paper itself, we write both the encrypted message and the value of N. That's what the players get at time A. (6) "The key" is simply the values of p and q. With them, it's easy to decrypt the message by hand (it's a sequence of simple 2-digit subtractions modulu 100). And of-course, verifying that N is indeed equal to pq is proof enough that I haven't pulled a fast one on them. Now, since this is a one-time-pad cipher, it should be theoretically unbreakable... unless the players can extract some information on the digits of p and q when they only know N. Can they? Or putting it differently: Is the problem of finding such information about p and q any easier than finding the factors themselves? (obviously the last digit of each prime must be 1,3,7 or 9 and they may be able to impose some limits on the first digit as well. But I doubt this alone will help in deciphering a 300-digit long message) Category:Blog posts